// 文件名：unordered_set_fast_filter.cpp
// 目的：快速对输入 URL 流去重，保留首次出现的顺序（稳定去重）。
// 思路：
//   - seen：unordered_set<string> 记录已出现过的 URL，insert 的返回 pair<it, bool> 中 second 表示是否新插入；
//   - filtered：vector<string> 存储首次出现的 URL，保持原始输入顺序；
//   - seen.reserve(incoming.size()) 预留容量以降低 rehash 次数。
// 复杂度：
//   - 均摊 O(N)（每个 URL 一次哈希插入检查）；空间 O(U)（U 为唯一 URL 数）。
// 注意：
//   - 若需大小写/规范化处理，应在插入前先 canonicalize（如去掉末尾斜杠、解码等）。

#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>

int main() {
    std::vector<std::string> incoming = {
        "https://example.com/",
        "https://example.com/about",
        "https://example.com/",
        "https://openai.com/",
        "https://example.com/about",
        "https://openai.com/research"
    };

    std::unordered_set<std::string> seen;
    seen.reserve(incoming.size());

    std::vector<std::string> filtered;
    filtered.reserve(incoming.size());

    for (const auto& url : incoming) {
        if (seen.insert(url).second) { // true 表示首次出现
            filtered.push_back(url);   // 只保留第一次出现的顺序
        }
    }

    std::cout << "Unique URLs:\n";
    for (const auto& url : filtered) {
        std::cout << "  " << url << '\n';
    }
    return 0;
}